package org.hot100.h279;

/**
 * @Author: wjy
 * @Date: 2022/3/3 10:17
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        System.out.println(solution.numSquares(5));

    }

    /**
     * dp nb!
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }

    public int numSquares2(int n) {
        int[] ints = new int[n + 1];

        for (int i = 1; i <= n; i++) {

            // bad
            ints[i] = i;

            for (int j = 1; i - j * j >= 0; j++) {

//                ints[i - j * j] + 1 说明：
//                1、为什么 ints[i - j * j]？
//                j * j 的目的是找出 i 范围内最大的平方数，如 当 n = 10 时，j = 3 可以构成 10 以内的最大平方数 9；
//                找到最大平方数的意义是什么呢？有题可知 “给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。”只有找到 i 内最大平
//                方数才能确定求出最小数量！综上所述找到最大平方数也就意味着找到最小数量，i 减去最大平方数的值，可以通过得到的结果
//                找到结果对应的最小数量！所以 ints[i - j * j] 其实是求出 i 范围内最大的平方数之外的最小数量
//                2、为什么 + 1？
//                由前面可知 ints[i - j * j] 得出 i 范围内最大的平方数之外的最小数量 加一则代表加上 i 内最大平方数的次数！
                ints[i] = Math.min(ints[i], ints[i - j * j] + 1);
            }
        }

        return ints[n];
    }

}
